#include <bits/stdc++.h>

using namespace std;

// 计算两堆石子的SG值
// 桌上有两堆石子，石头数量分别为a、b
// 任取一堆石子，将其移走，然后分割同一组的另一堆石子
// 从中取出若干个石子放在被移走的位置，组成新的一堆
// 操作完成后，组内每堆的石子数必须保证大于0
// 显然，被分割的一堆的石子数至少要为2
// 两个人轮流进行分割操作，如果轮到某人进行操作时，两堆石子数均为1，判此人输掉比赛
// 计算sg[a][b]的值并找到简洁规律
// 本文件仅为题目5打表找规律的代码

const int MAXN = 1001;
int dp[MAXN][MAXN];

void build()
{
    memset(dp, -1, sizeof dp);
}

int sg(int a, int b)
{
    if(a == 1 && b == 1) return 0;
    if(dp[a][b] != -1) return dp[a][b];
    bool appear[max(a, b) + 1];
    memset(appear, 0, sizeof appear);
    if(a > 1) // 分割 a
    {
        for(int l = 1, r = a - 1; l < a; ++l, --r)
        {
            appear[sg(l, r)] = true;
        }
    }
    if(b > 1) // 分割 b
    {
        for(int l = 1, r = b - 1; l < b; ++l, --r)
        {
            appear[sg(l, r)] = true;
        }
    }
    // mex 操作
    int ans = 0;
    for(int s = 0; s <= max(a, b); ++s)
    {
        if(!appear[s])
        {
            ans = s;
            break;
        }
    }
    return dp[a][b] = ans;
}

void f1() 
{
    cout << "石子数9以内所有组合的sg值" << endl;
    cout << endl;
    cout << "    ";
    for(int i = 1; i <= 9; i++) cout << i << " ";
    cout << endl;
    cout << endl;
    for(int a = 1; a <= 9; a++) 
    {
        cout << a << "   ";
        for(int b = 1; b < a; b++) cout << "X ";
        for(int b = a; b <= 9; b++) 
        {
            cout << sg(a, b) << " ";
        }
        cout << endl;
    }
}

void f2() 
{
    cout << "石子数9以内所有组合的sg值，但是行列都-1" << endl;
    cout << endl;
    cout << "    ";
    for(int i = 0; i <= 8; i++) cout << i << " ";
    cout << endl;
    cout << endl;
    for(int a = 1; a <= 9; a++) 
    {
        cout << (a - 1) << "   ";
        for(int b = 1; b < a; b++) cout << "X ";
        for(int b = a; b <= 9; b++) 
        {
            cout << sg(a, b) << " ";
        }
        cout << endl;
    }
}

// 返回status最低位的0在第几位
int lowZero(int status)
{
    int cnt = 0;
    while(status > 0)
    {
        if((status & 1) == 0) break;
        status >>= 1;
        ++cnt;
    }
    return cnt;
}

void f3() 
{
    cout << "测试开始" << endl;
    for(int a = 1; a < MAXN; a++) 
    {
        for(int b = 1; b < MAXN; b++) 
        {
            int sg1 = sg(a, b);
            int sg2 = lowZero((a - 1) | (b - 1));
            if (sg1 != sg2) cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
}

int main() 
{
    build();
    f1();
    cout << endl;
    cout << endl;
    f2();
    cout << endl;
    cout << endl;
    f3();

    return 0;
}